package com.fanwh.LinkedList;

/**
 * @program: DataStructure
 * @description: 单链表——带头结点
 * @author: Fanwh
 * @create: 2020-10-14 12:32
 **/
public class SingleLinkedList {

    private Node head = new Node(0,"");//头结点

    //在末尾添加元素，不考虑顺序
    public void add(Node node){
        if(head == null){
            System.out.println("链表不存在");
            return;
        }
        Node temp = head;//临时变量，用于遍历
        while (true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }

        temp.next = node;
    }

    //按顺序添加
    //1.首先要找待插入的位置
    //2.插入节点.next = temp.next;
    //  temp.next = 插入节点
    public void addByOrder(Node node){
        if (head == null){
            System.out.println("链表不存在");
            return;
        }

        Node temp = head;//临时变量，遍历
        boolean flag = false;//标志位，看是否出现编号相同的节点要插入单链表

        while (true){
            if(temp.next == null){//节点都已经到达尾部，都没找到要插入的位置，只能退出
                break;
            }else if (temp.next.num > node.num){
                break;
            }else if (temp.next.num == node.num){
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag){
            System.out.printf("编号为%d的节点已经存在，无法插入",node.num);
            System.out.println();
        }else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    public void list(){
        if(head == null){
            System.out.println("链表不存在");
        }
        Node temp = head.next;
        while (true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {

        //测试
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        Node node1 = new Node(1,"1");
        Node node2 = new Node(2,"2");
        Node node3 = new Node(3,"3");
        Node node4 = new Node(4,"4");
        Node node5 = new Node(5,"5");
        singleLinkedList.addByOrder(node1);
        singleLinkedList.addByOrder(node4);
        singleLinkedList.addByOrder(node3);
        singleLinkedList.addByOrder(node2);
        singleLinkedList.addByOrder(node5);
        singleLinkedList.list();
    }
}
class Node{
    public int num;
    public String name;
    Node next;//指向下一个节点

    //构造器
    public Node(int num, String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name +"'"+
                '}';
    }
}
